With the widespread use of computers in all aspects of modern life, there is an increasing demand to improve the human-machine interface through the use of visual information. Advances in graphical software and hardware have already improved the human-machine interface. Interactive graphics such as windowing environments for desk-top computers have also improved the ease of use and interactivity of computers and are common place today. As the price-performance ratio of hardware drops, the use of computer generated graphics and animation will become even more pervasive.
While there are numerous ways to categorize graphics processing, one common approach is to describe an image in terms of the dimensions of the objects that it seeks to represent. For example, a graphics system may represent objects in two dimensions (e.g., having x and y coordinates); in which case the graphics are said to be “two-dimensional”, and three dimensions (e.g., having x, y, and z coordinates), in which case the graphics are said to be “three-dimensional” (“3-D”).
The increasing ability of modern computers to efficiently handle 2-D and 3-D graphics has resulted in a growing variety of applications for computers, as well as fundamental changes in the interface between computers and their users. The availability of 3-D graphics is also becoming increasingly important to the growth of computer-aided design and computer-aided manufacturing (CAD/CAM), scientific and medical imaging, business applications, and electronic publishing.
One problem associated with the processing and display of 2-D and 3-D graphics is related to the amount of memory required to store the bitmap for even a single image. For example, the system may require 3.75 megabytes (Mb) of random access memory to support a display resolution of 1280×1024 (i.e., number of pixel columns and rows) and 24 bits of color information per pixel. This information, which again represents the image of a single screen, is stored in a portion of the computer's display memory known as a frame buffer.
The demands placed upon the system are further exacerbated by the complexity of the information that often must be processed to render an image. For example, the modeling of a three-dimensional surface is, in itself, a complex task. Surface modeling is performed by the application model and may involve the use of polygon meshes, parametric surfaces, or quadric surfaces. While a curved surface can be represented by a mesh of planar polygons, the “smoothness” of its appearance in the rendered image will depend both upon the resolution of the display and the number of individual polygons that are used to model the surface. The computations associated with high resolution modeling of complex surfaces based upon polygon meshes can be extremely resource intensive.
As intimated above, there is a demand to produce more realistic and interactive images. The term, “real-time,” is commonly used to describe interactive and realistic image processing systems. In a “real-time” system, the user should perceive a continuous motion of objects in a scene. In a CAD/CAM graphics application with real-time capabilities, the foreground components and view point should update very quickly and smoothly with minimal delay in response to a user's inputs. To produce such real-time effects, an image rendering system has to generate a new image at a sufficiently high rate such that the user perceives continuous motion of objects in a scene. The rate at which a new image is computed for display is referred to as the “computational” rate or the “computational frame” rate. The computational rate needed to achieve realistic effects can vary depending on how quickly objects move about the scene and how rapidly the viewing perspective changes. For a typical application, a real-time graphics system recomputes a new image at least twelve times a second to generate a series of images that simulate continuous motion. For high-quality animation applications, however, the computational rate must be significantly higher.
As introduced above, conventional graphics systems typically include a frame buffer. To generate an image, the graphic system renders all of the objects in a scene and stores the resulting image in this frame buffer. The system then transfers the rendered image data to a display. In a conventional graphics architecture, the entire frame buffer is erased and the scene is re-rendered to create a next frame's image. In this type of system, every object must be redrawn for each frame because the frame buffer is cleared between frames. Every object therefore is updated at the same rate, regardless of its actual motion in the scene or its importance to the particular application.
This conventional architecture presents several hurdles to producing highly realistic and interactive graphics. First, every object in a scene for a particular frame is rendered with the same priority and at the same update rate. As such, objects in the background that have little impact on the viewed image and are not moving, are re-rendered at the same rate as objects in the foreground that are moving more rapidly and have more surface detail. As a result, processing and memory resources are consumed in re-rendering background objects even though these background objects do not change significantly from frame to frame.
U.S. Pat. No. 5,574,835 to Duluk et al. discloses a method and apparatus for reducing the computations necessary to re-render foreground and background objects. The Duluk et al. reference teaches that the computations for determining whether a polygon lies within the perimeter of an object (i.e., is occulted) can be simplified by approximating the region inside the perimeter of the object with a set of simple shapes (circles, squares, and polyhedrons). However, by relying on approximations, Duluk et al. discloses that polygons lying inside an object and close to the surface, will still be rendered despite the fact that the polygon is actually occulted.
Thus, there is a need to overcome these and other problems of the prior art and to provide an efficient method of reducing the computations required to re-render foreground and background objects. The present invention, as illustrated in the following description, is directed to solving one or more of the problems set forth above.